package com.alex.algorithm.iguide.dp;


public class DPMatrix {
    public static void main(String[] args) {
        int[][] m = {{1, 2, 1}, {1, 3, 2}, {5, 7, 7}};
        System.out.println(minPathSum1(m));
        System.out.println("--------");
        System.out.println(minPathSum2(m));
    }

    public static int minPathSum1(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;

        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        // 初始化列
        for (int i = 1; i < row; ++i) {
            dp[i][0] = dp[i-1][0] + m[i][0];
        }
        // 初始化行
        for (int j = 1; j < col; ++j) {
            dp[0][j] = dp[0][j-1] + m[0][j];
        }
        // 生成矩阵
        for (int i = 1; i < row; ++i) {
            for (int j = 1; j < col; ++j) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + m[i][j];
                System.out.println("i:" + i + ",j:" + j + ",val:" + dp[i][j]);
            }
        }
        return dp[row - 1][col - 1];
    }

    public static int minPathSum2(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int more = Math.max(m.length,m[0].length);
        int less = Math.min(m.length,m[0].length);
        // 行列判断很关键
        boolean rowMore = m.length > m[0].length;
        int[] dp = new int[less];
        // 初始值
        dp[0] = m[0][0];
        System.out.println("dp[0]:" + dp[0]);
        for (int i = 1; i < less; ++i) {
            dp[i] = dp[i - 1] + (rowMore ? m[0][i] : m[i][0]);
            System.out.println("dp[" + i + "]:" + dp[i]);
        }
        // 滚动
        for(int i = 1; i < more; i++) {
            dp[0] = dp[0] + (rowMore ? m[i][0] : m[0][i]);
            System.out.println("dp[0]:" + dp[0]);
            for (int j = 1; j < less; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + (rowMore ? m[i][j] : m[j][i]);
                System.out.println("dp[" + j + "]:" + dp[j]);
            }
        }
        return dp[less - 1];
    }
}
